﻿// 303 小蜗的旅行.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>



using namespace std;

/*
http://oj.daimayuan.top/course/14/problem/657


小蜗想要完成一次说走就走的旅行，他来到了某旅行社进行咨询。

地图可以看做是一张 n个顶点 m条边的无向简单图，顶点编号从 1到 n
，每个顶点表示一座城市，在两个城市之间移动需要花费连接这两座城市的边的边权的代价。

小蜗是这家旅行社的vip用户，他拥有 k张打折券，在一次移动中他可以使用一张打折券，
使得这次移动的代价变成之前的一半，每条边只能使用一张打折券。

小蜗现在在 1号城市，他想知道他最少需要花费多少代价可以到达 n号城市，数据保证 1号城市和 n号城市两地连通。

输入格式
第一行三个整数 n,m,k
，表示图的顶点数（也就是城市数）、边数和打折券的数量。

接下来 m行，每行三个整数 x,y,z
，表示 x号城市和 y号城市之间有一条边权为 z的边。

输出格式
输出一行一个数表示答案。

样例输入
3 2 1
1 2 4
2 3 6
样例输出
7
数据规模
对于所有数据，保证 2≤n≤500,1≤m≤2000,1≤k≤10,1≤x,y≤n,1≤z≤10000，保证 z是偶数。
*/



int main()
{
    std::cout << "Hello World!\n";
}
 